import java.util.List;

public class MySingleList {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode (int val) {
            this.val=val;
        }
    }
    ListNode head;//表示当前链表的头节点
    //成员变量不会在函数结束回收

    public void createList(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        this.head=node1;
    }

    public void addFirst(int data){
    ListNode node=new ListNode(data);

    node.next=head;//就算是第一个也没有关系，此时就把空给了node，node也就是要null；
    head=node;//这里把新申请的节点和head联系起来。
    }

    public void display(){
        ListNode cur=head;
        //别让头节点乱跑
        //不然你下次咋顺藤摸瓜
        while(cur!=null){//用cur去遍历，如果等于空了，那就是走完了
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public int size(){
        ListNode cur=head;
        //别让头节点乱跑
        //不然你下次咋顺藤摸瓜
        int count=0;
        while(cur!=null){//用cur去遍历，如果等于空了，那就是走完了
            count++;
            //假设链表是一个，刚好加一次，后面不用管
            cur=cur.next;
        }
        return count;
    }
    public boolean contains(int key){
        ListNode cur=head;
        //别让头节点乱跑
        //不然你下次咋顺藤摸瓜
        while(cur!=null){//用cur去遍历，如果等于空了，那就是走完了
            if(cur.val==key)
            {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public void addLast(int data){
        if(head==null){
            head=new ListNode(data);
            //看错误去找地方，看异常
            //
        }
        //尾插法得先找到最后一个节点---怎么证明你找到最后的节点了？？
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=new ListNode(data);
        //这个直接就给最后插入
        //想想一开始就没有数据呢？
        //那不就有问题了
        //你去用cur.next那不就出错了？
    }
    public void addIndex(int index,int data){
        if(index==0){
            addFirst(data);//头插法
        }else if(index==size()){//这里有坑，就是你要插入0位置，但是可以被隐藏起来，你还是要知道
            addLast(data);
        }else{

            //这里的这个次数，
            ListNode cur=findIndexSubOne(index);
            ListNode node =new ListNode(data);
            node.next=cur.next;
            cur.next=node;
        }
        //非法情况呢？？
        //尽量封装--此处封装了根据调用者给的数字，来找到前一个结点

    }
    private ListNode findIndexSubOne(int index){
        ListNode cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    public void remove(int key){
        if(head==null){
            return;
        }
        if(head.val==key){
            head=head.next;
            //因为这个代码只删掉第一个遇到的，所以只删除一次，不会有问题

        }
        //1.找到你要删除的节点的前一个节点
        //此时你要删除的节点del=cur。next
        ListNode cur=searchPrev(key);
        if(cur==null){
            System.out.println("没有你要找的数字");
            return ;
        }
        ListNode del=cur.next;
        cur.next=del.next;
        //你前面只是找到了


    }
    private ListNode searchPrev(int key){
        ListNode cur=head;
        while(cur.next !=null){
            if(cur.next.val==key){//你此处使用cur的下一个去判断，你可以找到上一个
                //你要是直接让他走下来，你确返回不去了

                return cur;
            }
            cur=cur.next;//for循环的变化条件
        }
        return null;
    }
    public void clear(){
        this.head=null;
        //这里自己不去回收空间
        //java中可以自动回收空间
    }
    public void removeAllKey(int key){
        //用循环不是面试官想要的写法
        //面试官需要的是你一次遍历去删掉所有的key
        //你用一个前后指针，不断地跑
        //后指针定位，前指针判断是否需要删除的值，以及找到下一个，让前指针跑
        //
        if(head==null){
            return;
        }
        //你可以用循环，把每次头节点的满足条件的值都删掉
        //不然你只删一次，删除之后也还是呢？
            ListNode prev=head;
            ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
                //此处代表删除了一个，如果后面有一个一样的，那么都是前指针跑
            }else{
                //这种情况，就是下一个不是，需要让两个指针朝向后面移动
                //当是最后一个的时候，也是没有问题的
                //但是你怎么删掉prev所指向的那个呢？？
                 prev=cur;
                 cur=cur.next;
            }
        }
        if(head.val==key){
            head=head.next;
            //这个必须要在最后
            //你如果在前面，就会可能删完还需要删
            //那么就要用循环了
        }
    }

        //
    //使用一个curNext来保存原本断开的头节点
    //然后对前面断开的进行，一个头插法
    //从头开始走，
    //循环主要是让后半段不断地往下走
    //用cur！=null来作为条件，
    //这样curNext才有意义
    //你第一步这个代码是很抽象的，也就是断开、然后把curNext找到
    //然后往下走
    public void reserveList(){
        if(head==null){
            return;
        }
        if(head.next==null){
            //只有一个节点
            return;
        }
        //ListNode cur=head;
        ListNode cur=head.next;
        //这一步是记录下第二个节点，
        head.next=null;
        //然后把连接断开，这样就不用对第一个进行操作、
        //对第一个操作会循环的
        //自己存放自己的地址
        //但是下一步在，head里去存放
        while(cur!=null) {
            ListNode curNext = cur.next;
            //第一步要有个滞空操作，因为你不滞空，你其他的方法都是按照最后一个是空来结束遍历的
            //这样你在调用其他方法的时候就会出现问题
            //好的办法是从外面去断开第一个，然后滞空，对后面的继续使用前面的方法就可以了
            cur.next=head;
            head=cur;
            cur=curNext;
        }
    }
    //建议反转之后，把新的头节点都还回去

}
